# 典型的 二分发查数字  二分发适合的是有序的 考虑到时间复杂度
from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if (len(nums) == 0):
            return [-1, -1]

        res1 = -1
        res2 = -1
        left = 0
        right = int((len(nums)) / 2)
        while (left < right):
            if (nums[right - 1] >= target):
                right = int((left + right) / 2)
            else:
                left = right
                right = int((left + len(nums)) / 2)
        res1 = left
        list2 = nums[::-1]
        left = 0
        right = int((len(list2)) / 2)
        while (left < right):
            if (list2[right - 1] <= target):
                right = int((left + right) / 2)
            else:
                left = right
                right = int((left + len(list2)) / 2)
        res2 = len(nums) - left - 1
        if (nums[res1] != target):
            return [-1, -1]
        return [res1, res2]


lll = Solution()
print(lll.searchRange([1,3,5,6,7,8,8,8,8,9,11,11,12,13,14,15], 9))
